package previous.Test_0228;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //解码方法：将数字解码成字符
//    1.状态表示
//    dp[i]表示：以位置为结尾，解码方法的总数
//    2.状态转移方程：
//    1-9可以解码成一个字母
//    10-26可以解码成一个字母
//    dp[i]分为s[i]单独解码，
//    以及s[i]与s[i-1]解码

    public int numDecodings1(String s) {
        int n=s.length();
        int[] dp=new int[n];
        char[] c=s.toCharArray();
        //单独解码
        //如果字符不为0
        if(c[0]!='0') dp[0]=1;
        //处理边界情况
        if(n==1) return dp[0];
        //两个字符解码
        if(c[0]!='0' && c[1]!='0') dp[1]+=1;
        //注意字符要相减
        int t=(c[0]-'0')*10+c[1]-'0';
        if(t>=10 && t<=26) dp[1]+=1;
        for (int i = 2; i < n; i++) {
            //单独解码
            if(c[i]!='0') dp[i]+=dp[i-1];
            //两个字符解码
            t=(c[i-1]-'0')*10+c[i]-'0';
            if(t>=10 && t<=26) dp[i]+=dp[i-2];;
        }
        return dp[n-1];
    }
    public int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        char[] c=s.toCharArray();
        //单独解码
        //如果字符不为0
        dp[0]=0;
        if(c[0]!='0') dp[1]=1;
        //处理边界情况
        if(n==1) return dp[0];
        for (int i = 2; i < n; i++) {
            //单独解码
            if(c[i-1]!='0') dp[i]+=dp[i-1];
            //两个字符解码
            int t=(c[i-2]-'0')*10+c[i-1]-'0';
            if(t>=10 && t<=26) dp[i]+=dp[i-2];;
        }
        return dp[n];
    }
    //不同路径1
    //dp[i][j]=dp[i-1][j]+dp[i][j-1];
    public int uniquePaths(int m, int n) {
          int[][] dp=new int[m+1][n+1];
          dp[0][1]=1;
          int i,j;
        for (i = 1; i <=m ; i++) {
            for (j= 1; j <=n ; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    //不同路径2：有障碍物
    //dp[i][j]=dp[i-1][j]+dp[i][j-1];
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n=obstacleGrid.length;
        int m=obstacleGrid[0].length;
        int[][] dp=new int[n+1][m+1];
        dp[0][1]=1;
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=m ; j++) {
                if(obstacleGrid[i-1][j-1]==1) dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[n][m];
    }
    //珠宝的最高价值
    //dp[i][j]代表路径的最大值
    //dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i][j]
    public int jewelleryValue(int[][] frame) {
            int n=frame.length;
            int m=frame[0].length;
            int[][] dp=new int[n+1][m+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i][j];
            }
        }
        return dp[n][m];
    }
}
